
/**
 * 四叉树
 * 管理的对象需要实现ITreeObj接口
 */
export default class QuadTree {
    protected root: TreeNode = null;
    protected maxDepth: number = 7;
    protected maxCount: number = 10;
    public constructor(xMin: number, xMax: number, zMin: number, zMax: number, depth?: number, count?: number) {
        this.init(xMin, xMax, zMin, zMax, depth, count);
    }
    /**
     * 
     * @param xMin 
     * @param xMax 
     * @param zMin 
     * @param zMax 
     * @param depth 四叉树最大深度，根据四叉树最大尺寸与碰撞体最小尺寸来设置
     * @param count 四叉树的节点包含的最大对象数，插入对象数量大于该值时，节点将分裂为4个子节点
     */
    public init(xMin: number, xMax: number, zMin: number, zMax: number, depth?: number, count?: number) {
        if (!!depth && depth > 0) this.maxDepth = depth;
        if (!!count && count > 0) this.maxCount = count;
        if (!this.root) {
            this.root = Pool.get(xMin, xMax, zMin, zMax, this.maxDepth, this.maxCount);
        } else {
            this.root.reset();
            this.root.set(xMin, xMax, zMin, zMax, this.maxDepth, this.maxCount);
        }
    }
    /**
     * 预先创建好子节点
     * @param depth 子节点最大深度，默认为树的最大深度
     */
    public createChildren(depth?: number) {
        if (undefined === depth || depth < 0 || depth > this.maxDepth) {
            depth = this.maxDepth;
        }
        this.root.splitTo(depth);
    }
    public reset() {
        if (!!this.root) {
            this.root.reset();
        }
    }
    /**
     * 从四叉树中移除对象
     * 动态更新对象在四叉树中的位置时，需要先将其从当前所属的节点中移除
     * @param obj       要移除的对象
     * @param nodeId    对象当前所属的节点id
     */
    public removeObj(obj: any, nodeId?: number) {
        if (undefined === nodeId) {
            let id = obj[treeNodeId];
            if (!!id && id > 0) {
                let node = AllNodes[nodeId];
                if (!!node) {
                    node.removeObj(obj);
                    return;
                }
            }
        } else {
            let node = AllNodes[nodeId];
            if (!!node) {
                node.removeObj(obj);
                return;
            }
        }
        this.root.removeObj(obj);
    }
    /**
     * 向四叉树中插入对象
     * @param obj 要插入的对象
     * @returns 对象所属的节点的id
     */
    public insertObj(obj: any): number {
        // if (!this.root) {
        //     console.error("插入对象错误：四叉树未初始化！");
        //     return null;
        // }
        let node = this.root.insertObj(obj);
        // cc.log("节点深度：", node.depth);
        return node;
    }
    /**
     * 查找可能与对象碰撞的所有对象
     * @param obj 要检测的对象
     */
    public getObjs(obj: any): any[] {
        let arr = [];
        let rect = TreeNode.getObjRect(obj);
        this.root.getObjs(rect, arr);
        return arr;
    }
    public getObjsByAABB(rect: Rect) {
        let arr = [];
        this.root.getObjs(rect, arr);
        return arr;
    }
}
export const treeNodeId = "treeNodeId";
//节点
export class TreeNode {
    protected static _autoId: number = 1;
    protected _id: number;
    public get Id() { return this._id; }
    public parent: TreeNode = null;
    public children: TreeNode[] = null;
    public objs: any[];
    public xMin: number;
    public xMax: number;
    public zMin: number;
    public zMax: number;
    public centerX: number;
    public centerY: number;
    public depth: number;
    public count: number;//完全包含在节点内的对象数量
    public maxDepth: number = 7;
    public maxCount: number = 10;

    public constructor(xMin: number, xMax: number, zMin: number, zMax: number, maxDepth: number, maxCount: number, parent?: TreeNode) {
        this._id = TreeNode._autoId++;
        AllNodes[this.Id] = this;
        this.set(xMin, xMax, zMin, zMax, maxDepth, maxCount, parent);
    }
    public set(xMin: number, xMax: number, zMin: number, zMax: number, maxDepth: number, maxCount: number, parent?: TreeNode) {
        this.xMin = xMin;
        this.xMax = xMax;
        this.zMin = zMin;
        this.zMax = zMax;
        this.centerX = (this.xMin + this.xMax) * 0.5;
        this.centerY = (this.zMin + this.zMax) * 0.5;
        this.maxDepth = maxDepth;
        this.maxCount = maxCount;

        this.objs = [];
        this.count = 0;
        this.parent = parent;
        if (!!parent) {
            this.depth = parent.depth + 1;
        } else {
            this.depth = 0;
        }
    }
    public splitTo(depth: number) {
        if (this.depth >= depth) return;
        this.createChildren();
        for (let i = this.children.length - 1; i >= 0; --i) {
            this.children[i].splitTo(depth);
        }
    }
    public split() {
        this.createChildren();
        let objs = this.objs;
        this.objs = [];
        this.count = 0;
        for (let i = objs.length - 1; i >= 0; --i) {
            let obj = objs[i];
            let rect = TreeNode.getObjRect(obj);
            let area = this.getArea(rect);
            if (area != Area.self) {
                this.children[area].insertIntoSelf(obj);
            } else {
                this.insertIntoSelf(obj);
            }
        }
        this.count = this.objs.length;
    }
    protected createChildren() {
        if (!!this.children) return;
        let x = this.centerX;
        let y = this.centerY;
        this.children = [];
        this.children[Area.area0] = Pool.get(x, this.xMax, y, this.zMax, this.maxDepth, this.maxCount, this);
        this.children[Area.area1] = Pool.get(this.xMin, x, y, this.zMax, this.maxDepth, this.maxCount, this);
        this.children[Area.area2] = Pool.get(this.xMin, x, this.zMin, y, this.maxDepth, this.maxCount, this);
        this.children[Area.area3] = Pool.get(x, this.xMax, this.zMin, y, this.maxDepth, this.maxCount, this);

    }
    public removeObj(obj: any) {
        let rect = TreeNode.getObjRect(obj);
        if (!this.children) {
            this.removeFromSelf(obj);
        } else {
            let area = this.getArea(rect);
            if (area == Area.self) {
                this.removeFromSelf(obj);
            } else {
                this.children[area].removeObj(obj);
            }
        }
    }
    protected removeFromSelf(obj: any) {
        let index = this.objs.indexOf(obj);
        if (index >= 0) {
            this.objs.splice(index, 1);
            this.count--;
            obj[treeNodeId] = -1;
        }
    }

    public insertObj(obj: any): number {
        if (!!this.children) {
            return this.insertIntoChildren(obj);
        } else {
            if (this.objs.length < this.maxCount || this.depth >= this.maxDepth) {
                return this.insertIntoSelf(obj);
            } else {
                this.split();
                return this.insertIntoChildren(obj);
            }
        }
    }
    protected insertIntoChildren(obj: any): number {
        let rect = TreeNode.getObjRect(obj);
        let area = this.getArea(rect);
        if (area != Area.self) {
            return this.children[area].insertObj(obj);
        } else {
            return this.insertIntoSelf(obj);
        }
    }
    protected getArea(rect: Rect) {
        if (!this.children) return Area.self;
        if (rect.xMin >= this.centerX) {
            if (rect.zMin >= this.centerY) {
                return Area.area0;
            } else if (rect.zMax <= this.centerY) {
                return Area.area3;
            }
        } else if (rect.xMax <= this.centerX) {
            if (rect.zMin >= this.centerY) {
                return Area.area1;
            } else if (rect.zMax <= this.centerY) {
                return Area.area2;
            }
        }
        return Area.self;
    }
    protected insertIntoSelf(obj: any): number {
        this.objs.push(obj);
        this.count++;
        obj[treeNodeId] = this.Id;
        return this.Id;
    }
    /**矩形1是否完全包含矩形2 */
    public static contain(rect1: Rect, rect2: Rect): boolean {
        return rect1.xMin <= rect2.xMin
            && rect1.xMax >= rect2.xMax
            && rect1.zMin <= rect2.zMin
            && rect1.zMax >= rect2.zMax;
    }
    /**获取对象的矩形范围 */
    public static getObjRect(obj: any): Rect {
        return obj.getAABB();
    }
    /**
     * 获取节点内包含的对象
     */
    public getObjs(rect: Rect, out: any[]) {
        if (!TreeNode.cross(rect, this)) return;
        for (let i = this.count - 1; i >= 0; --i) {
            out.push(this.objs[i]);
        }
        if (!!this.children) {
            let area = this.getArea(rect);
            if (area == Area.self) {
                for (let i = this.children.length - 1; i >= 0; --i) {
                    this.children[i].getObjs(rect, out);
                }
            } else {
                this.children[area].getObjs(rect, out);
            }
        }
    }

    /**矩形1与矩形2是否相交 */
    public static cross(rect1: Rect, rect2: Rect): boolean {
        return rect1.xMin <= rect2.xMax
            && rect1.xMax >= rect2.xMin
            && rect1.zMin <= rect2.zMax
            && rect1.zMax >= rect2.zMin;
    }

    public reset() {
        this.parent = null;
        for (let i = this.objs.length - 1; i >= 0; --i) {
            this.objs[i][treeNodeId] = -1;
        }
        this.objs = [];
        this.count = 0;
        this.depth = 0;
        if (!!this.children) {
            let nodes = this.children;
            this.children = null;
            for (let i = nodes.length - 1; i >= 0; --i) {
                Pool.put(nodes[i]);
            }
        }
    }
}
enum Area {
    area0 = 0,
    area1,
    area2,
    area3,
    self,
}
type Rect = {
    xMin: number,
    xMax: number,
    zMin: number,
    zMax: number
};
//节点对象池
class Pool {
    protected static nodes: TreeNode[] = [];
    public static get(xMin: number, xMax: number, zMin: number, zMax: number, maxDepth: number, maxCount: number, parent?: TreeNode) {
        if (this.nodes.length > 0) {
            let node = this.nodes.pop();
            node.set(xMin, xMax, zMin, zMax, maxDepth, maxCount, parent);
            return node;
        } else {
            return new TreeNode(xMin, xMax, zMin, zMax, maxDepth, maxCount, parent);
        }
    }
    public static put(node: TreeNode) {
        node.reset();
        this.nodes.push(node);
    }
}
//按id记录所有节点
let AllNodes: { [id: number]: TreeNode } = {};
